/*
 * IntervalTree.java
 * 
 * Created by demory on Mar 16, 2009, 9:03:15 PM
 * 
 * Copyright 2008 David D. Emory
 * 
 * This file is part of Five Points. See <http://www.fpdev.org> for
 * additional information regarding the project.
 * 
 * Five Points is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Five Points is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Five Points.  If not, see <http://www.gnu.org/licenses/>.
 */

package org.fpdev.core.algo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * A general purpose integer-based centered interval tree based on the
 * description in <i>Computational Geometry</i> by M. de Berg, M. van Kreveld,
 * M. Overmars, and O. Schwarzkopf, pp. 212-218.
 *
 * Construction time is O(n log n), query time is O(log n + m), m being the
 * size of the result set, and storage space is O(n).
 *
 * @author demory
 */
public class IntervalTree<I extends IntegerInterval> {


  private ITreeNode root_;

  public IntervalTree(Set<I> intervals) {
    root_ = constructTree(intervals, "");
  }


  // MAIN CONSTRUCTION METHOD & HELPER METHODS/CLASSES

  private ITreeNode constructTree(Set<I> intervals, String lead) {
    //if(lead.length()>=20) return null;

    //lead += "-";
    //System.out.println(lead+"cT size = "+intervals.size());

    if(intervals.isEmpty()) return new ITreeLeafNode();

    // construct an array of endpoints
    int[] endpoints = new int[2 * intervals.size()];
    int i = 0;
    for(I interval : intervals) {
      endpoints[i] = interval.getLower();
      endpoints[i+1] = interval.getUpper();
      i += 2;
    }

    double xMid = median(endpoints);

    //System.out.println(lead+"xMid="+xMid);
    Set<I> iLeft = new HashSet<I>();
    Set<I> iMid = new HashSet<I>();
    Set<I> iRight = new HashSet<I>();

    for(I interval : intervals) {
      if(interval.getLower() > interval.getUpper()) {
        System.out.println("WARNING: Bad Interval: "+interval.toString());
        continue;
      }
      //if(xMid==54000) System.out.println(lead+"("+interval.getLower()+" to "+interval.getUpper()+")");
      if(interval.getUpper() < xMid)
        iLeft.add(interval);
      else if(interval.getLower() <= xMid && xMid <= interval.getUpper())
        iMid.add(interval);
      else if(xMid < interval.getLower())
        iRight.add(interval);
    }

    List<I> lLeft = new ArrayList<I>(iMid);
    Collections.sort(lLeft, new LowerComparator());

    List<I> lRight = new ArrayList<I>(iMid);
    Collections.sort(lRight, new UpperComparator());
    Collections.reverse(lRight);

    return new ITreeBranchNode(
            constructTree(iLeft, lead),
            constructTree(iRight,lead),
            xMid,
            lLeft,
            lRight);

  }

  private double median(int[] integers) {
    Arrays.sort(integers);
    int middle = integers.length/2;
    if(integers.length % 2 == 1)
      return integers[middle];
    else
      return (double) (integers[middle-1] + integers[middle]) / 2.0;
  }

  private class LowerComparator implements Comparator<I> {

    public int compare(I o1, I o2) {
      return new Integer(o1.getLower()).compareTo(o2.getLower());
    }

  }

  private class UpperComparator implements Comparator<I> {

    public int compare(I o1, I o2) {
      return new Integer(o1.getUpper()).compareTo(o2.getUpper());
    }

  }

  // MAIN QUERY METHOD & HELPERS

  public Set<I> query(int point) {
    return query(root_, point, new HashSet<I>());
  }

  private Set<I> query(ITreeNode node, int point, Set<I> results) {
    if(!node.isLeaf()) {

      if(point < ((ITreeBranchNode) node).getXMid()) {
        for(I interval : ((ITreeBranchNode) node).getLLeft()) {
          if(interval.contains(point)) results.add(interval);
          else break;
        }
        query(node.getLeft(), point, results);
      }
      else {
        for(I interval : ((ITreeBranchNode) node).getLRight()) {
          if(interval.contains(point)) results.add(interval);
          else break;
        }
        query(node.getRight(), point, results);
      }

    }
    return results;
  }

  // NODE CLASSES

  private abstract class ITreeNode {

    protected ITreeNode left_, right_;

    public abstract boolean isLeaf();

    public ITreeNode getLeft() { return left_; }

    public ITreeNode getRight() { return right_; }
  }

  private class ITreeLeafNode extends ITreeNode {

    public ITreeLeafNode() {
    }

    @Override
    public boolean isLeaf() {
      return true;
    }
  }

  private class ITreeBranchNode extends ITreeNode {

    private double xMid_;

    private List<I> lLeft_, lRight_;

    public ITreeBranchNode(ITreeNode left, ITreeNode right, double xMid, List<I> lLeft, List<I> lRight) {
      left_ = left;
      right_ = right;
      xMid_ = xMid;
      lLeft_ = lLeft;
      lRight_ = lRight;
    }

    public double getXMid() {
      return xMid_;
    }

    public List<I> getLLeft() {
      return lLeft_;
    }

    public List<I> getLRight() {
      return lRight_;
    }

    @Override
    public boolean isLeaf() {
      return false;
    }

  }


}
